#include <iostream>

using namespace std;

/*
Given a simplified version of regular expressions, implement a function which will 
match a pattern against a string and return true or false depending on whether or 
not they match.

Pattern Syntax:
'.' Matches any character at that position in the subject string
'*' Modifies the previous element to match zero or many

Note:'*' is meaningless alone, so "*" or "**" is invalid input

Any other character matches its exact value only (case sensitive)
*/


bool IsMatch( char p, char s)
{
	return ( p == s || (p=='.'&& s!='\0'));
}

bool Match( char *str, char* p)
{
	if(*p=='\0') 
		return (*str=='\0');
	
	if( *(p+1) != '*')
	{
		if(IsMatch(*p, *str))
		{
			return Match( str+1, p+1);
		}
		return false;
	}

	// *(p+1) is '*'
	while(IsMatch(*p, *str)) 
	{
		if(Match(str, p+2)) 
			return true;
		str++;
	}

	return Match(str, p+2);
}

typedef struct _STRINGS{
	char * String;
	char * Pattern;
	bool IsMatch;
} STRING, *PSTRING;

int const EntryCount = 12;
STRING TestStrings[EntryCount]=
{
	{"abbdefg", "ab*defg", true},
	{"abcdefg", "a.*bcdefg", true},
	{"abcdefg", "am*bcdefg", true},
	{"abbbb", ".*", true},
	{"abbbb", "a.*", true},
	{"abbbb", "a.*.*", true},
	{"abbbb", "a.*.*", true},
	{"abbcccg", "ab*.*g", true},
	{"abbbcccg", "a.*.*", true},
	{"abbbcccg", "a.*.*.*", true},
	{"abcccc", "abcc*", true},
	{"abbbb", "a.*d", false},
};

int main()
{
	bool succeed= true;
	for( int i=0; i<EntryCount; i++ )
	{
		if( Match(TestStrings[i].String, TestStrings[i].Pattern ) != TestStrings[i].IsMatch )
		{
			if( TestStrings[i].IsMatch )
				printf("Pattern %s match string %s is expected to be TRUE\n", TestStrings[i].Pattern, TestStrings[i].String);
			else
				printf("Pattern %s match string %s is expected to be FALSE\n", TestStrings[i].Pattern, TestStrings[i].String);

			succeed= false;
		}
	}

	if( succeed )
		cout<<"Tests Match succeed!!!"<<endl;

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}